我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
    string tmp;
    vector<string> res;
    vector<string> board = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void DFS(int pos, string digits)
    {
        if (pos == digits.size())
        {
            res.push_back(tmp);
            return;
        }
        int num = digits[pos] - '0';
        for (int i = 0; i < board[num].size(); i++)
        {
            tmp.push_back(board[num][i]);
            DFS(pos + 1, digits);
            tmp.pop_back();
        }
    }
    vector<string> letterCombinations(string digits)
    {
        if (digits.size() == 0)
            return res;
        DFS(0, digits);
        return res;
    }
};

思路

  1. 先按照每个数字对应的多个字母创建一个表格，为了方便所以直接使用数字作为下标，所以你会看见前两个是””，是空的。
  2. 主函数，首先判断传入的数字字符串是否是空的，如果是，直接返回空。
  3. 进入DFS函数，传入的参数有位置pos和题目给定的数字字符串。
  4. 刚开始这个判断可能有些迷惑，后面会解释。
  5. 将传入的数字字符串中的第一个数字提取出来，化为整形便于处理，注意这里的**- ‘0’**很常用。
  6. 进入一个循环，往tep中添加元素，这里我们假设题目给定的数字是”23”，那么push的第一个字符就是’a’。
  7. 此时调用DFS(pos + 1, digits)后会再次进入到这个循环，由于pos加一，所以这里的num也加一，拿到的数就是下表为3的第一个字符了，即d，此时的tmp为[‘a’, ‘d’]
  8. 再次进入DFS(pos + 1, digits)，此时的pos为2，与size相同，满足之前说的判断条件，此时的tmp被push进res中，同时出发return，DFS函数终止。
  9. 回到之前的循环中，触发**tmp.pop_back()**，d被删除，此时的tmp为[‘a’]
  10. 仍然在循环中，注意此时的pos仍然是1，i也为1，触发push_back，此时的tmp为[‘a’, e’]
  11. 同理，在内层循环结束时，res会变成[“ad”, “ae”, “af”]
  12. 继续外层循环，此时a变成b了，继续进入内层循环，后续同理。
  13. 总体思想为回溯